易于使用的计算机

虚拟化

虚拟化可以分成两部分

虚拟化CPU

目标

让用户觉得自己的单核CPU电脑能够同时运行多个程序

Mechanism

进程切换

进程调度

在进程切换的时候,OS应该选择哪一个进程占用CPU才是合理且高效的呢?

Policies

First In, First Out (FIFO)

Shortest Job First (SJF)

Shortest Time-to-Completion First (STCF)

Round Robin(RR)

多级反馈队列

多级反馈队列是一种实际运用相对较多的调度算法,在Windows NT内核中都有用到,我们单独拿出来讲

虚拟化内存

目标

Mechanism

Policies

并发

线程

同步原语

用锁实现thread-safe的数据结构

A general design tip, which is useful in concurrent code as well as elsewhere, is to be wary of control flow changes that lead to function returns, exits, or other similar error conditions that halt the execution of a function. Because many functions will begin by acquiring a lock, allocating some memory, or doing other similar stateful operations, when errors arise, the code has to undo all of the state before returning, which is error-prone. Thus, it is best to structure code to minimize this pattern.

  • 所以我们可以对以上的代码进行改进,得到一份更加鲁棒的concurrent链表的实现
    • Alt text
  • 并行队列
    • 不像单链表只能从表头开始操作,队列可以从队头和队尾同时进行操作,所以我们可以对对头和队尾分别加锁
    • Alt text
    • 注意这份代码中使用了一个哨兵节点,这也是我们在实现普通队列的时候应该做的(还记得判断队列为空还是为满的条件吗?)
  • 并行哈希表
    • Alt text
    • 使用前面建立的并行链表,我们就能实现一个非常高效的并行哈希表
    • 当然使用的是开放式冲突解决策略中的独立链表法
  • 使用同步原语解决一些问题

    持久化

    I/O设备

    Interlude: File and Directories

    file

    directories

    怎么组织同一个目录下的文件或者子目录?
    现代操作系统一般使用B树。

    对于目录和纯文件来说,二者存储的信息有什么区别?
    纯文件,存储的是文件的内容,对于目录,存储的是目录下的子目录和文件以及它们对应的inode number。

    Very Simple File System(VSFS)

    Locality and The Fast File System

    VSFS的效率太低了,我们需要更加快速的操作系统,Fast File System (FFS)。

    Crash Consistency: FSCK and Journaling

    Alt text

    Solution #1: The File System Checker

    Solution #2: Journaling (or Write-Ahead Logging)

    Data Journaling

    在下面的示例中,我们需要更新某个文件的内容,相应的会写一部分用户数据(Db),更新bitmap(B[v2]),更新对应的inode(I[V2])

    Metadata Journaling(ordered journaling)

    Solution #3: Other Approaches